package main

import "go-leetcode/leetcode/utils"

// 19. 删除链表的倒数第 N 个结点
func main() {
	//listNode := utils.GetListNodeByArray([]int{5, 6, 1, 8, 4, 5})
	//target := 4
	listNode := utils.GetListNodeByArray([]int{1, 2})
	target := 2

	pointListNode := listNode
	for pointListNode != nil {
		print(pointListNode.Val, " ")
		pointListNode = pointListNode.Next
	}
	println(" ")

	node := removeNthFromEnd(listNode, target)

	pointResNode := node
	println("转换为")
	for pointResNode != nil {
		print(pointResNode.Val, " ")
		pointResNode = pointResNode.Next
	}
	return
}

func removeNthFromEndStack(head *utils.ListNode, n int) *utils.ListNode { // 这是什么鸡巴栈，这不是类似辅助数组了吗
	var nodes []*utils.ListNode
	dummy := &utils.ListNode{Next: head}
	for node := dummy; node != nil; node = node.Next {
		nodes = append(nodes, node)
	}
	prev := nodes[len(nodes)-1-n]
	prev.Next = prev.Next.Next
	return dummy.Next
}

func removeNthFromEnd(head *utils.ListNode, n int) *utils.ListNode {
	// 双指针，第一个指针先前进n个节点
	fast := head

	dummy := &utils.ListNode{
		Val:  0,
		Next: head,
	}
	slow := dummy

	for i := 1; i < n; i++ {
		if fast.Next == nil {
			return head
		}
		fast = fast.Next
	}

	for fast.Next != nil {
		fast = fast.Next
		slow = slow.Next
	}

	// 删除slow的Next的节点，如果是头部节点要特殊处理

	deleteNode := slow.Next
	slow.Next = slow.Next.Next
	deleteNode.Next = nil

	return dummy.Next
}

// 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
//
//
//
//示例 1：
//
//
//输入：head = [1,2,3,4,5], n = 2
//输出：[1,2,3,5]
//示例 2：
//
//输入：head = [1], n = 1
//输出：[]
//示例 3：
//
//输入：head = [1,2], n = 1
//输出：[1]
//
//
//提示：
//
//链表中结点的数目为 sz
//1 <= sz <= 30
//0 <= Node.val <= 100
//1 <= n <= sz
//
//
//进阶：你能尝试使用一趟扫描实现吗？
